/**
 * 元素个数大于数组长度一般的叫做主元素
 * 要求找主元素
 * 
 * 简单想法，统计每个元素的个数，然后比较
 * 建立一个数组，下标是ai的值，数组元素是ai出现的次数
 * 这样两边遍历可以找到主元素
 * O(n) 和 O(n)
 * 如何优化呢，主元素是出现次数最多的那个
 * 出现次数最多的就可以和其他的抵消掉？
 * 从0开始遍历，当前数字的计数位1，如果和下一个数字不同
 * 那么就将计数减一（也就是和不同的元素抵消掉了
 * 如果相同就+1
 * 如果计数位0，那么从下一个元素开始计数，初始值仍为1
 * O(n)和O(1)
 * 这里使用一遍遍历解决
 */
#include<iostream>
#include<vector>
using namespace std;
int findMain(vector<int> arr){
    int count=1;
    int m=arr[0];
    for(int i=1;i<arr.size();i++){
        if(m==arr[i]){
            count++;
        }else{
            count--;
        }
        if(count==0){//重新设置主元素
            m=arr[i];
            count=1;
        }
    }
    return m;
}
int main(void){
    vector<int> test={1,1,2};
    auto res=findMain(test);
    cout<<res<<endl;
    return 0;
}